#define _CRT_SECURE_NO_WARNINGS 1
#include"sort.h"

//插入排序
void InsertSort(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		int end = i;//记录有序序列最后一个元素下标
		int tmp = a[end+1];//待插入元素
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		//代码执行到此位置有两种情况:
		//1.待插入元素找到应插入位置（break跳出循环到此）。
		//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）。
		a[end + 1] = tmp;
	}
}

//希尔排序
void SheelSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;
		int i = 0;
		for (i = 0; i < n-gap; i++)
		{
			int end = i;//记录有序序列最后一个元素下标
			int tmp = a[end + gap];//待插入元素
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			//代码执行到此位置有两种情况:
			//1.待插入元素找到应插入位置（break跳出循环到此）。
			//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）。
			a[end + gap] = tmp;
		}
	}
}

////选择排序（寻找最小值）
//void SelectSort(int* a, int n)
//{
//	int i = 0;
//	for (i = 0; i < n; i++)
//	{
//		int start = i;//记录每轮起始下标
//		int min = start;//记录每轮最小值下标
//		while (start < n)
//		{
//			if (a[start] < a[min])
//			{
//				min = start;
//			}
//			++start;
//		}
//		std::swap(a[i], a[min]);//最小值与该躺首元素交换位置
//	}
//}

//选择排序（同时寻找最小值和最大值）
void SelectSort(int* a, int n)
{
	int left = 0;//记录本轮首个位置
	int right = n - 1;//记录本轮最后一个位置
	while (left < right)
	{
		int minIndex = left;//本轮最小下标
		int maxIndex = left;//本轮最大下标
		int i = 0;
		for (i = left; i <= right; ++i)
		{
			if (a[i] < a[minIndex])
				minIndex = i;
			if (a[i] > a[maxIndex])
				maxIndex = i;
		}
		//放置最大值和最小值
		std::swap(a[minIndex], a[left]);
		if (maxIndex == left)
		{
			maxIndex = minIndex;//如果本轮最大值的下标刚好是首元素，在上步已与最小值交换位置，要更新当前最大值下标
		}
		std::swap(a[maxIndex], a[right]);

		++left;
		--right;
	}
}